//Sun Oct  2 14:38:54 PDT 2011
import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class QuickSums {
	public int minSums(String numbers, int sum) {
		int N = numbers.length();
		long[][] dp = new long[N][sum + 1];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= sum; j++) {
				dp[i][j] = Long.MAX_VALUE - 1;
			}
		}
		for (int i = 0; i < N; i++) {
			long tmp = Long.parseLong(numbers.substring(0, i + 1));
			if (tmp <= sum)
				dp[i][(int) tmp] = 0;
			else
				break;
		}
		// for (int i = 0; i < N; i++) {
		// for (int j = 0; j <= sum; j++) {
		// System.out.print(dp[i][j]);
		// System.out.print(", ");
		// }
		// System.out.println();
		// }
		// System.out.println();
		for (int i = 0; i < N; i++) {
			for (int k = 1; k <= i; k++) {
				long tmp = Long.parseLong(numbers.substring(k, i + 1));
				if (tmp > sum)
					continue;
				for (int j = 0; j <= sum; j++) {
					if (j >= tmp)
						dp[i][j] = Math.min(dp[i][j],
								dp[k - 1][j - (int) tmp] + 1);
				}
			}
		}
		// for (int i = 0; i < N; i++) {
		// for (int j = 0; j <= sum; j++) {
		// System.out.print(dp[i][j]);
		// System.out.print(", ");
		// }
		// System.out.println();
		// }
		if (dp[N - 1][sum] == Long.MAX_VALUE - 1)
			return -1;
		return (int) dp[N - 1][sum];
	}
	// <%:testing-code%>
}
// Powered by [KawigiEdit] 2.0!
